package com.example.code2022;

import com.alibaba.fastjson.JSON;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: dangwen
 * @createDate: 2022/4/22
 * 167. 两数之和 II - 输入有序数组
 * 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
 */
public class P167 {

    public static void main(String[] args) {
        int[] nums = new int[]{2,7,11,15};
        System.out.println(JSON.toJSONString(byCursor(nums, 9)));;
    }

    // 使用map空间换时间
    public static int[] byMap(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int value = target - nums[i];
            if (map.containsKey(value)){
                return new int[]{map.get(value) + 1, i +1};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
    // 左右指针，左加右减
    public static int[] byCursor(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while (left < right){
            if (nums[left] + nums[right] < target){
                left ++;
            } else if (nums[left] + nums[right] > target){
                right--;
            }else {
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[0];
    }
}
